import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class L144_2 {

    public static void main(String[] args) {
//        new Solution().preorderTraversal();
    }


    static class Solution {
        public List<Integer> preorderTraversal(TreeNode root) {
            ArrayList<Integer> list = new ArrayList<>();
            if (root == null) {
                return list;
            }

            Stack<TreeNode> stack = new Stack<>();
            stack.push(root);
            while (!stack.isEmpty()) {
                TreeNode node = stack.pop();
                list.add(node.val);
                if (node.right != null) {
                    stack.push(node.right);
                }
                if (node.left != null) {
                    stack.push(node.left);
                }
            }
            return list;
        }

    }

//    static class Solution {
//        public List<Integer> inorderTraversal(TreeNode root) {
//            ArrayList<Integer> list = new ArrayList<>();
//            dg(root, list);
//            return list;
//        }
//
//        private void dg(TreeNode root, ArrayList<Integer> list) {
//            if (null == root) {
//                return;
//            }
//            dg(root.left, list);
//            list.add(root.val);
//            dg(root.right, list);
//
//        }
//    }
}
